/**
 * 折半插入排序：优化直接插入排序,也可以对于链表排序
 * 空间复杂度:O(1)
 * 时间复杂度:O(n*n)
 * 算法稳定性:稳定
 */

#include <stdio.h>

void Insert_binary_sort(int A[], int n);

void print(int a[], int n);


int main()
{
	int a[10]={1,4,6,2,3,8,6,9,0,2};
	Insert_sort(a,10);
	return 0;
}

void print(int a[], int n)
{
	for(int i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
}

void Insert_binary_sort(int A[], int n)
{
	int i,j,low,high,mid;
	for(int i=2;i<n;i++)
	{
		A[0]=A[i];		//A[i]存放到A[0]
		low=1,high=i-1;	//设置者半查找范围
		while(low<=high)//折半查找
		{
			mid=(low+high)/2;//取中间点
			if(A[mid]>A[0]) high=mid-1;//中间点值大于A[0]值，插入位置在左边
			else low=mid+1;//中间点值小于A[0]，插入位置在右边
		}
		for(j=i-1; j>=high+1;j--)
		{
			A[j+1]=A[j];	//后移元素，空出插入位置
		}
		A[high+1]=A[0];		//插入操作
	}
}